package com.hdu.other.binarySearch;

import java.util.Arrays;

public class lc719 {

    class Solution {
        public int smallestDistancePair(int[] nums, int k) {
            Arrays.sort(nums);
            int l = 0, r = nums[nums.length - 1] - nums[0], ans = 0;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (f(nums, mid) >= k) {
                    ans = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            return ans;
        }

        int f(int[] nums, int limit) {
            int ans = 0;
            for (int i = 0; i < nums.length; i++) {
                int j = i + 1;
                while (j < nums.length && nums[j] - nums[i] <= limit) {
                    j++;
                }
                ans += j - i - 1;
            }
            return ans;
        }
    }

}
